#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solve1(const vector<int> &arr) {
  vector<int> sums(arr.size(), 0);

  if (arr.empty()) { return 0; }
  if (arr.size() == 1) { return arr[0]; }

  // 说明 arr 至少有 2 个元素
  sums[0] = arr[0];
  sums[1] = max(arr[0], arr[1]);

  for (int i = 2; i < arr.size(); ++i) {
    // case1 arr[i] + sums[i - 2]
    // case2 arr[i]
    // case3 sums[i - 1]
    // 决定 sums[i] 的值
  }

  return sums.back();
}

vector<int> solve2(const vector<int> &arr) {
  vector<int> sums(arr.size(), 0);
  vector<vector<int>> expressions;
  
  if (arr.empty() || arr.size() == 1) { return arr; }

  // 说明 arr 至少有 2 个元素
  sums[0] = arr[0];
  expressions.push_back({arr[0]});

  sums[1] = max(arr[0], arr[1]);
  expressions.push_back({max(arr[0], arr[1])});

  for (int i = 2; i < arr.size(); ++i) {
    int x = arr[i] + sums[i - 2];
    int y = arr[i];
    int z = sums[i - 1];
    int m = max({x, y, z});

    sums[i] = m;
    if (m == x) {
      vector<int> tmp = expressions[i - 2];
      tmp.push_back(arr[i]);
      expressions.push_back(tmp);
    }
    else if (m == y) {
      expressions.push_back({arr[i]});
    }
    else {
      // m == z
      expressions.push_back(expressions[i - 1]);
    }
  }

  return expressions.back();
}



int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
